#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// 定义一个结构体表示内存中的页框
typedef struct Frame {
  int page_num;
  int last_used;
} Frame;

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */

void lru_page_replacement(char *queue_frames, int num_frames) {
  Frame *frames = (Frame *)malloc(num_frames * sizeof(Frame));
  // 初始化页框
  for (int i = 0; i < num_frames; i++) {
      frames[i].page_num = -1;
      frames[i].last_used = -1;
  }
  int time = 0;  // 记录访问时间
  char *token = strtok(queue_frames, ",");
  while (token != NULL) {
      int page_num = atoi(token);
      int found = 0;
      // 检查页面是否在内存中
      for (int i = 0; i < num_frames; i++) {
          if (frames[i].page_num == page_num) {
              found = 1;
              frames[i].last_used = time;
              break;
          }
      }
      if (!found) {
          int lru_index = 0;
          int min_time = frames[0].last_used;
          // 找到最近最少使用的页框
          for (int i = 1; i < num_frames; i++) {
              if (frames[i].last_used < min_time) {
                  min_time = frames[i].last_used;
                  lru_index = i;
              }
          }
          frames[lru_index].page_num = page_num;
          frames[lru_index].last_used = time;
      }
      // 输出当前内存状态
      printf("Access:%d,Frames: [", page_num);
      for (int i = 0; i < num_frames; i++) {
          if (i != 0) {
              printf(",");
          }
          if (frames[i].page_num != -1) {
              printf("%d", frames[i].page_num);
          } else {
              printf("-1");
          }
      }
      printf("]\n");
      time++;
      token = strtok(NULL, ",");
  }
  free(frames);
}